package m_HashTable;

import java.util.Arrays;
import java.util.TreeMap;

public class HashTable_1<K extends Comparable<K>, V> {

    private final int[] capacity	//经科学测试 比较合适的容量
            = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};

    private static final int upperTol = 10;   //如何量化hash冲突的严重程度呢？   平均hash冲突的长度（hash(key)对应的ds长度）就可以体现； 我们可以规定一个上限。下限 平均长度，来作为resize的指标；
    private static final int lowerTol = 2;
    private int capacityIndex = 0;

    private TreeMap<K, V>[] hashtable;
    private int size;
    private int M;

    public HashTable_1(){
        this.M = capacity[capacityIndex];
        size = 0;
        hashtable = new TreeMap[M];
        for(int i = 0 ; i < M ; i ++)
            hashtable[i] = new TreeMap<>();
    }

    private int hash(K key){
        return (key.hashCode() & 0x7fffffff) % M;    //0x是16进制的意思，x是小写X；计算机里常见的内存地址等都带个0x，都是2进制的压缩存储；
    }

    public int getSize(){
        return size;
    }

    public void add(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key))
            map.put(key, value);
        else{
            map.put(key, value);
            size ++;

            if(size >= upperTol * M && capacityIndex + 1 < capacity.length){  
                capacityIndex ++;
                resize(capacity[capacityIndex]);
            }
        }
    }

    public V remove(K key){
        V ret = null;
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key)){
            ret = map.remove(key);
            size --;

            if(size < lowerTol * M && capacityIndex - 1 >= 0){  //缩容时不必担心放不放得下，因为不管多小 都能通过hash冲突来存入；
                capacityIndex --;
                resize(capacity[capacityIndex]);
            }
        }
        return ret;
    }

    public void set(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if(!map.containsKey(key))
            throw new IllegalArgumentException(key + " doesn't exist!");

        map.put(key, value);
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashtable[hash(key)].get(key);
    }

    private void resize(int newM){
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for(int i = 0 ; i < newM ; i ++)
            newHashTable[i] = new TreeMap<>();

        int oldM = M;   
        this.M = newM;
        for(int i = 0 ; i < oldM ; i ++){   //hash表长度改变 原hash返回值失效 所以得拿数据
            TreeMap<K, V> map = hashtable[i];  
            for(K key: map.keySet())
                newHashTable[hash(key)].put(key, map.get(key));   //这种写法就是直接面向问题面向目标的写法；
        }

        this.hashtable = newHashTable;
    }
    
	@Override
	public String toString() {
		return "HashTable_1 [size=" + size + ",capa="+ M + ", data=" + Arrays.toString(hashtable) + "]";
	}

	public static void main(String[] args) {
		HashTable_1<Integer, Integer> test = new HashTable_1<>();
//		for (int i = 0; i < 16; i++) {
//			test.add(i, i%5);
//		}
//		System.out.println(test);
		for (int i = 0; i < 1000; i++) {
			test.add(i, i%20);
		}
		System.out.println(test);
	}
}